package com.chj.zhongji.class14;

public class Code01_BestTimetoBuyandSellStock1 {

	public static int maxProfit(int[] prices) {
		if (prices == null || prices.length == 0) {
			return 0;
		}
		int min = prices[0];
		int ans = 0;
		for (int i = 0; i < prices.length; i++) {
			min = Math.min(min, prices[i]);
			ans = Math.max(ans, prices[i] - min);
		}
		return ans;
	}

//	https:// leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/bao-li-mei-ju-dong-tai-gui-hua-chai-fen-si-xiang-b/
	public static int maxProfitDp(int[] prices) {
		int len = prices.length;
		if (len < 2) {
			return 0;
		}

		// 0：用户手上不持股所能获得的最大利润，特指卖出股票以后的不持股，非指没有进行过任何交易的不持股
		// 1：用户手上持股所能获得的最大利润

		// 注意：因为题目限制只能交易一次，因此状态只可能从 1 到 0，不可能从 0 到 1
		int[][] dp = new int[len][2];
		dp[0][0] = 0;
		dp[0][1] = -prices[0];
		for (int i = 1; i < len; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
			dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
		}
		return dp[len - 1][0];
	}

	public static int maxProfitDp2(int[] prices) {
		int len = prices.length;
		if (len < 2) {
			return 0;
		}

		// 0：不进行任何操作
		// 1：用户执行了一次买入操作
		// 2：用户执行了一次卖出操作

		// 状态转移方程：
		// dp[i][0] 永远等于 0
		// dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
		// dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])

		// 注意：如果是 `[7, 6, 5, 4, 3]` 这种波动，应该不交易，
		// 因此输出是：max(dp[len - 1][0], dp[len - 1][2])

		int[][] dp = new int[len][3];
		dp[0][0] = 0;
		dp[0][1] = -prices[0];
		// 这里状态 2 不应该有值，设置为 0 不影响正确性
		dp[0][2] = 0;
		for (int i = 1; i < len; i++) {
			// 可以不显式赋值，因为 int 的初值就是 0
			dp[i][0] = 0;
//			 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
			dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
			dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
		}
		return Math.max(dp[len - 1][0], dp[len - 1][2]);
	}

	public static void main(String[] args) {
		{
			int[] arr = { 7, 1, 5, 3, 6, 4 };
			System.out.println(maxProfit(arr));
			System.out.println(maxProfitDp(arr));
			System.out.println(maxProfitDp2(arr));
		}

		{
			int[] arr = { 7, 6, 4, 3, 1 };
			System.out.println(maxProfit(arr));
			System.out.println(maxProfitDp(arr));
			System.out.println(maxProfitDp2(arr));
		}
	}

}
